package previous.Test_0327;

import java.util.*;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Blue_bridge {
    //星际旅行
    public static void main1(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int n=scan.nextInt();
        int m=scan.nextInt();
        int Q=scan.nextInt();
        Map<Integer,List<Integer>> haspMap=new HashMap<Integer, List<Integer>>();
        //建图
        for(int i=1;i<=n;i++) {
            haspMap.put(i, new ArrayList<>());
        }
        for(int i=0;i<m;i++) {
            int a=scan.nextInt();
            int b=scan.nextInt();
            haspMap.get(a).add(b);
            haspMap.get(b).add(a);
        }
        long sum=0;
        for(int i=0;i<Q;i++) {
            int x=scan.nextInt();
            int y=scan.nextInt();
            //拓扑排序
            Queue<Integer> queue=new LinkedList<Integer>();
            queue.add(x);
            int[] dis=new int[n+1];
            Arrays.fill(dis, -1);//初始化
            dis[x]=0;//起始位置为0
            while(!queue.isEmpty()) {
                int t=queue.poll();
                if(dis[t]>y) {
                    continue;
                }
                for(int w:haspMap.getOrDefault(t, new ArrayList<>())) {
                    if(dis[w]==-1) {
                        dis[w]=dis[t]+1;
                        if(dis[w]<=y) {
                            queue.add(w);
                        }
                    }
                }
            }
            int count=0;
            for(int j=1;j<=n;j++) {
                if(dis[j]!=-1 && dis[j]<=y) {
                    count++;
                }
            }
            sum+=count;
        }
        double avg=(double)sum/Q;
        System.out.printf("%.2f\n",avg);
        System.out.println("No");

        scan.close();
    }
    //字符统计
    public static void main2(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        String string=scan.nextLine();
        char[] c=string.toCharArray();
        Map<Character, Integer> hashMap=new HashMap<Character, Integer>();
        StringBuffer stringBuffer=new StringBuffer();
        for(int i=0;i<c.length;i++) {
            hashMap.put(c[i],hashMap.getOrDefault(c[i], 0)+1);
        }
        int max=Integer.MIN_VALUE;
        for(int x:hashMap.values()) {
            if(x>max) {
                max=x;
            }
        }
        for(Character m:hashMap.keySet()) {
            if(hashMap.get(m)==max) {
                stringBuffer.append(m);
            }
        }
        System.out.println(stringBuffer.toString());
        scan.close();
    }

}
